package nine.test_9_5;

import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;

public class TestMain3 {

        public static void main(String[] args) {
            int[] sequence = {2, 2, 3, 4, 5};
            int x = 3;
            int minOperations = minOperationsToMakeMultiple(sequence, x);
            System.out.println("最少操作次数: " + minOperations);
        }

        public static int minOperationsToMakeMultiple(int[] sequence, int x) {
            int n = sequence.length;
            int totalSum = 0;

            for (int num : sequence) {
                totalSum += num;
            }

            int remainder = totalSum % x;

            if (remainder == 0) {
                return 0;
            }

            int[] dp = new int[x];
            Arrays.fill(dp, Integer.MAX_VALUE);

            for (int i = 0; i < n; i++) {
                int currentRemainder = sequence[i] % x;
                for (int j = 0; j < x; j++) {
                    int newRemainder = (j + currentRemainder) % x;
                    dp[newRemainder] = Math.min(dp[newRemainder], dp[j] + 1);
                }
            }

            return dp[0];
        }


}
